Stacks & Queues | What, how and where to use

Stacks and Queues are two very commonly used dynamic data structures that provide us with a unique way of handling data. The usage of these types of data structures varies and depends on the problem as all other tools in software engineering.

Let's get more deeply into each of these data structures to understand how they work and where we could use them.

Stack

A Stack data structure is a collection of data that implements a Last In First Out (LIFO) principle. In Java, stacks are an abstract class that extends the vector class.

To make it simpler imagine a bucket, add all items from the top and stack them up on top of each other. You only have access to the top of the stack. When you remove an item from the top of the stack, the item you get is the last item you added.

Stack has four basic methods:

• The push method which adds an item to the top of the stack
• The pop method which removes the item at the top
• The peek method which gets the item at the top without removing it from the stack
• The isEmpty method which is used to check if the stack is empty

Use cases

Generally, a common usage of the stack data structure is for a quick forward/backwards navigation within an app.

Let’s take for example an internet browser, on which we get a back navigational button. Keeping track of the URLs a user has visited is a good use case for a stack. With the URL of the current site a user is viewing, to be on the top of the stack we can move backwards by popping URLs from the stack.

Another cool usage is implementing an undo feature in text editors. We store previous text edits in a stack and go back through it.

Additionally, take a look at the code below that reverses a given string by utilizing a simple java stack data structure

// create a stack of characters
Stack<Character> st = new Stack<Character>();

// convert string to reverse into an array of characters
char[] arr = str.toCharArray();

// iterate chars array and push each char into the stack
for(char c : arr){
  st.push(c);
}

// pop all chars from the stack into the new array
for(int i = 0; i < arr.length; i++){
  arr[i] = st.pop();
}

// print reversed string
System.out.println(new String(arr));

Queue

A Queue data structure is a collection of data that implements a First In First Out (FIFO) principle. A Queue in Java is an interface, which means we need to implement it on a concrete class. Usually, we use it on LinkedList or PriorityQueue classes.

Queues provide us with access to the beginning and the end of the list, respectively called the head and the tail.

Simply imagine a tube where you add items in from one end and they come out the other end in the same order you added them.

Queues have three basic methods similar to stacks:

• The add method which adds an item through the tail of the queue, also known as enqueue method
• The poll method which gets and removes the first item on the head of the queue, also known as dequeue
• The peek method which gets the item on the head but does not remove it from the queue

Use cases

Generally, we use a queue whenever we want to process items in the same order as they requested processing.

Some common usages of a queue data structure are when, for example, an application implements a first in first serve principle such as IO buffers and files IO asynchronous requests.

Other similar use cases we may want to use a queue, is when we share resources with other apps or systems such as CPU (i.e. multithreading) and DISK scheduling.

Queues are also used in searches such as a Breadth-First Search method of a graph or tree as well as in CACHE systems.

In general, it is a good practice to use a queue data structure when you have multiple requests to serve at once but not the ability to do so. It is fair to serve them in a FIFO principle.

To show you a practical example where we can use a queue, I wrote below a java method that searches a tree if it has a path to a given node.

// custom node class
public static class Node {

  int id;

  Node left;

  Node right;

  public Node(int id){
    this.id = id;
  }
}


public static boolean hasPathBFS(Node source, int destination){

  // create a queue for nodes to be checked
  Queue<Node> nextToCheck = new LinkedList<Node>();

  // create set to temporarily store the id of the nodes we check
  HashSet<Integer> visited = new HashSet<>();

  // add source node into the queue for checking
  nextToCheck.add(source);

  // check nodes in queue
  while(!nextToCheck.isEmpty()){

    // get head node and remove from queue
    Node node = nextToCheck.poll();

    // head node null check
    if(node == null) return false;

    // check node
    if(node.id == destination) return true;

    // mark node as visited
    if(!visited.contains(node.id)) visited.add(node.id);

    // add children in the next to check queue
    nextToCheck.add(node.left);
    nextToCheck.add(node.right);
  }

  // if no path found
  return false;
}

Conclusion

In this article, we covered what a Stack and a Queue data structures are, their principles and basic functionalities, as well as some common usage examples.

Stacks and Queues are very simple yet powerful tools that are now at your disposal to use in solving problems as you may find appropriate.

I hope you enjoyed this article and stay tuned for more!